package madixin.t24;

class Solution {
    /**
     * 递归
     */
    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        // Nodes to be swapped
        ListNode firstNode = head;
        ListNode secondNode = head.next;

        // Swapping
        firstNode.next = swapPairs(secondNode.next);
        secondNode.next = firstNode;

        // Now the head is the second node
        return secondNode;
    }

    /**
     * 非递归
     */
    public ListNode swapPairs1(ListNode head) {

        ListNode dummy = new ListNode(-1);
        dummy.next = head;

        ListNode preNode = dummy;

        while (head != null && head.next != null) {

            ListNode firstNode = head;
            ListNode secondNode = head.next;

            preNode.next = secondNode;
            firstNode.next = secondNode.next;
            secondNode.next = firstNode;

            //jump
            preNode = firstNode;
            head = firstNode.next;

        }
        // Now the head is the second node
        return dummy.next;
    }
}